package UnionSearchSet;

/**
 * @Author Fizz Pu
 * @Date 2021/8/12 下午4:53
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
public class Union {
}

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n==0) return false;
        DSU dsu = new DSU(n);
        for(int i=1;i<=n;i++){
            int step = nums[i-1];
            for(int j=1;j<=step;j++){
                if(i+j<=n){
                    dsu.union(i,i+j);
                }
            }
        }
        return dsu.isConnected(1,n);
    }
    // 并查集模版 路径压缩+rank
    class DSU {
        int[] weight; // 表示数量
        int[] arr;
        DSU(int N){
            arr = new int[N+1];
            weight = new int[N+1];
            for(int i=0;i<N+1;i++) arr[i] = i;
            for(int i=1;i<N+1;i++) weight[i] = 1;
        }
        // 查
        int find(int x){
            if(arr[x]!=x){
                arr[x] = find(arr[x]);
            }
            return arr[x];
        }
        // 并
        void union(int x,int y){
            int px = arr[x];
            int py = arr[y];
            if(px==py) return;
            if(weight[px]<weight[py]){
                arr[px] = py;
                weight[py] += weight[px];
            }else {
                arr[py] = px;
                weight[px] += weight[py];
            }
        }
        // 判断
        boolean isConnected(int x, int y){
            return find(x)==find(y);
        }
    }


}
